package com.fyt.recover.order;

import java.util.*;

public class BucketSortDoubleVersion {

    public static void BucketSortDoubleVersion(double [] arr){
        double maxValue=0;
        double minValue=0;

        //桶的数量
        int bucketCount=arr.length;

        //构建桶
        List<List<Double>> buckets=new ArrayList<>(bucketCount);
        for (int i = 0; i <bucketCount ; i++) {
            buckets.add(new ArrayList<>());
        }


        OptionalDouble max= Arrays.stream(arr).max();
        if(max.isPresent()) {
           maxValue = max.getAsDouble();
        }
        OptionalDouble min=Arrays.stream(arr).min();
        if(min.isPresent()){
            minValue =min.getAsDouble();
        }



        //归一化,映射到整数数组(桶的序号),
         Double range= maxValue-minValue;
        for (int i = 0; i <arr.length ; i++) {
          int index= (int) ((arr[i]-minValue)/range*(bucketCount-1));
          buckets.get(index).add(arr[i]);

        }
         //将桶的元素拷贝回去arr
        int index=0;
        for(List<Double> bucket:buckets){
            for (double num:bucket){
                arr[index++]=num;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
